#include<stack>
#include <iostream>
#include "rbtree.h"

namespace QinChat{
    namespace Core{
		template<typename T>
		RBTreeNode<T>* RBTree<T>::NIL = new RBTreeNode<T>();

        template <typename T>
        RBTree<T>::RBTree(){
        }

        template <typename T>
        RBTree<T>::~RBTree(){
            Clearn(m_pRoot);
        }

        template <typename T>
        bool RBTree<T>::IsContains(const T& k) const{
            return nullptr != SearchNode(k);
        }

        template <typename T>
        bool RBTree<T>::GetMinmum(T& minElem) const{
            if (nullptr != m_pRoot){
                minElem = GetMinmum(m_pRoot)->data;
                return true;
            }

            return false;
        }

        template <typename T>
        bool RBTree<T>::GetMaxmum(T& minElem) const{
            if (nullptr != m_pRoot){
                minElem = GetMaxmum(m_pRoot)->data;
                return true;
            }

            return false;
        }

        template <typename T>
        bool RBTree<T>::GetSuccessor(const T& k,T& ret) const{
            RBTreeNode<T>* pNode = SearchNode(k);
            if (nullptr == pNode){
                return false;
            }

            pNode = GetSuccessor(pNode);
            if (nullptr == pNode){
                return false;
            }

            ret = pNode->data;
            return true;
        }

        template <typename T>
        bool RBTree<T>::GetPredecessor(const T& k,T& ret) const{
            RBTreeNode<T>* pNode = SearchNode(k);
            if (nullptr == pNode){
                return false;
            }

            pNode = GetPredecessor(pNode);
            if (nullptr == pNode){
                return false;
            }

            ret = pNode->data;
            return true;
        }
        
        template <typename T>
        bool RBTree<T>::Insert(const T& k){
            RBTreeNode<T>* pNewNode = new RBTreeNode<T>();
            pNewNode->data = k;
            pNewNode->pParent = nullptr;
            pNewNode->pLeft = nullptr;
            pNewNode->pRight = nullptr;
            pNewNode->color = RED;

            if (nullptr == pNewNode){
                return false;
            }

            if (nullptr == m_pRoot){
                m_pRoot = pNewNode;
				InsertFixup(pNewNode);
                return true;
            }

            RBTreeNode<T>* pCurNode = m_pRoot;
            RBTreeNode<T>* pParentNode = nullptr;
            while (nullptr != pCurNode){
                pParentNode = pCurNode;

                if (pCurNode->data > k){
                    pCurNode = pCurNode->pLeft;
                }
                else{
                    pCurNode = pCurNode->pRight;
                }
            }

            pNewNode->pParent = pParentNode;
            if (pParentNode->data > k){
                pParentNode->pLeft = pNewNode;
            }
            else{
                pParentNode->pRight = pNewNode;
            }

            InsertFixup(pNewNode);
            return true;
        }
        
        template <typename T>
        bool RBTree<T>::Delete(const T& k){
            RBTreeNode<T>* pNode = SearchNode(k);
            if (nullptr == pNode){
                return false;
            }

            RBTreeNode<T>* pDNode = nullptr, *pTNode = nullptr;
            if (nullptr == GetLeft(pNode) || nullptr == GetRight(pNode)){
                pDNode = pNode;
            }
            else {
                pDNode =  GetSuccessor(pNode);
            }

            if (nullptr != GetLeft(pDNode)){
                pTNode = pDNode->pLeft;
            }
            else{
                pTNode = pDNode->pRight;
            }

			if (nullptr != pTNode) {
				pTNode->pParent = GetParent(pDNode);
			}
			else {
				pTNode = NIL;
				pTNode->pParent = GetParent(pDNode);

			}
            
            if (nullptr == GetParent(pDNode)){
                m_pRoot = pTNode;
            }
            else if (pDNode == GetParent(pDNode)->pLeft){
                pDNode->pParent->pLeft = pTNode;
            }
            else{
                pDNode->pParent->pRight = pTNode;
            }

            if (pDNode != pNode){
                pNode->data = pDNode->data;
            }

            if (pDNode->color == BLACK){
                DeleteFixup(pTNode);
            }

            delete pDNode;
            pDNode = nullptr;
            return true;
        }
        
        template <typename T>
        void RBTree<T>::InorderWalk()const{
            if (nullptr == m_pRoot){
                return;
            }

            std::stack<RBTreeNode<T>* >s;
            RBTreeNode<T>* pTempNode = m_pRoot;
            while ((nullptr != pTempNode || !s.empty()) && NIL != pTempNode){
                if (nullptr != pTempNode ){
                    s.push(pTempNode);
                    pTempNode = pTempNode->pLeft;
                }
                else{
                    pTempNode = s.top();
                    s.pop();
                    
                    std::cout<<pTempNode->data<<" : ";
                    if (pTempNode->color == BLACK){
                        std::cout<<"Black"<<std::endl;
                    }
                    else{
                        std::cout<<"Red"<<std::endl;
                    }

                    pTempNode = pTempNode->pRight;
                }
            }
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetRoot() const{
            return m_pRoot;
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetParent(RBTreeNode<T>* pNode) const{
			if (nullptr == pNode) {
				return nullptr;
			}
            return pNode->pParent;
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetLeft(RBTreeNode<T>* pNode) const{
			if (nullptr == pNode) {
				return nullptr;
			}
            return pNode->pLeft;
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetRight(RBTreeNode<T>* pNode) const{
			if (nullptr == pNode) {
				return nullptr;
			}
            return pNode->pRight;
        }

        template <typename T>
        T RBTree<T>::GetKey(RBTreeNode<T>* pNode) const{
			if (nullptr == pNode) {
				return T();
			}
            return pNode->data;
        }

        template <typename T>
        RBTreeColor RBTree<T>::GetColor(RBTreeNode<T>* pNode) const{
			if (nullptr == pNode) {
				return BLACK;
			}
            return pNode->color;
        }

        template <typename T>
        void RBTree<T>::SetColor(RBTreeNode<T>* pNode, RBTreeColor color){
            if (nullptr == pNode){
                return;
            }

            pNode->color = color;
        }

        template <typename T>
        void RBTree<T>::LeftRotate(RBTreeNode<T> *pNode){
            RBTreeNode<T>* pRightNode = pNode->pRight;
            pNode->pRight = pRightNode->pLeft;
            if (nullptr != pRightNode->pLeft){
                pRightNode->pLeft->pParent = pNode;
            }

            pRightNode->pParent = pNode->pParent;
            if (nullptr == pNode->pParent){
                m_pRoot = pRightNode;
            }
            else if (pNode == GetParent(pNode)->pLeft){
                GetParent(pNode)->pLeft = pRightNode;
            }
            else{
                GetParent(pNode)->pRight = pRightNode;
            }

            pRightNode->pLeft = pNode;
            pNode->pParent = pRightNode;
        }

        template <typename T>
        void RBTree<T>::RightRotate(RBTreeNode<T> *pNode){
            RBTreeNode<T>* pLeftNode = pNode->pLeft;
            pNode->pLeft = pLeftNode->pRight;
            if (nullptr != pLeftNode->pRight){
                pLeftNode->pRight->pParent = pNode;
            }

            pLeftNode->pParent = pNode->pParent;
            if (nullptr == pNode->pParent){
                m_pRoot = pLeftNode;
            }
            else if (pNode == GetParent(pNode)->pLeft){
                GetParent(pNode)->pLeft = pLeftNode;
            }
            else{
                GetParent(pNode)->pRight = pLeftNode;
            }

            pLeftNode->pRight = pNode;
            pNode->pParent = pLeftNode;
        }
        
        template <typename T>
        void RBTree<T>::InsertFixup(RBTreeNode<T> *pNode){
            RBTreeNode<T>* pGrandNode = nullptr, *pUncleNode = nullptr;

            while (m_pRoot != pNode && RED == GetColor(GetParent(pNode))){
                pGrandNode = GetParent(GetParent(pNode));
                if (GetParent(pNode) == GetLeft(pGrandNode)){
                    pUncleNode = pGrandNode->pRight;
                    if (RED == GetColor(pUncleNode)){
                        SetColor(GetParent(pNode), BLACK);
                        SetColor(pUncleNode, BLACK);
                        SetColor(pGrandNode, RED);
                        pNode = pGrandNode;
                    }
                    else{
                        if (pNode == GetParent(pNode)->pRight){
                            pNode = GetParent(pNode);
                            LeftRotate(pNode);
                        }

                        SetColor(GetParent(pNode), BLACK);
                        pGrandNode = GetParent(GetParent(pNode));
                        SetColor(pGrandNode, RED);
                        RightRotate(pGrandNode);
                    }
                }
                else{
                    pUncleNode = pGrandNode->pLeft;
                    if (RED == GetColor(pUncleNode)){
                        SetColor(GetParent(pNode), BLACK);
                        SetColor(pUncleNode, BLACK);
                        SetColor(pGrandNode, RED);
                        pNode = pGrandNode;
                    }
                    else{
                        if (pNode == GetParent(pNode)->pLeft){
                            pNode = GetParent(pNode);
                            RightRotate(pNode);
                        }

                        SetColor(GetParent(pNode), BLACK);
                        pGrandNode = GetParent(GetParent(pNode));
                        SetColor(pGrandNode, RED);
                        LeftRotate(pGrandNode);
                    }
                }
            }

            SetColor(m_pRoot, BLACK);
        }

        template <typename T>
        void RBTree<T>::DeleteFixup(RBTreeNode<T> *pNode){
            while (m_pRoot != pNode && BLACK == GetColor(pNode)){
                RBTreeNode<T>* pBrotherNode = nullptr;
                if (pNode == GetParent(pNode)->pLeft){
                    pBrotherNode = GetParent(pNode)->pRight;
                    if (RED == GetColor(pBrotherNode)){
                        SetColor(pBrotherNode, BLACK);
                        SetColor(GetParent(pNode), RED);
                        LeftRotate(GetParent(pNode));
                        pBrotherNode = GetParent(pNode)->pRight;
                    }
                    if (BLACK == GetColor(pBrotherNode->pLeft) && BLACK == GetColor(pBrotherNode->pRight)){
                        SetColor(pBrotherNode, RED);
                        pNode = GetParent(pNode);
                    }
                    else{
                        if (BLACK == GetColor(pBrotherNode->pRight)){
                            SetColor(pBrotherNode->pLeft, BLACK);
                            SetColor(pBrotherNode, RED);
                            RightRotate(pBrotherNode);
                            pBrotherNode = GetParent(pNode)->pRight;
                        }

                        SetColor(pBrotherNode, GetColor(GetParent(pNode)));
                        SetColor(GetParent(pNode), BLACK);
                        SetColor(GetParent(pBrotherNode)->pRight, BLACK);
                        LeftRotate(GetParent(pNode));
                        pNode = m_pRoot;
                    }
                }
                else{
                    pBrotherNode = GetParent(pNode)->pLeft;
                    if (RED == GetColor(pBrotherNode)){
                        SetColor(pBrotherNode, BLACK);
                        SetColor(GetParent(pNode), RED);
                        RightRotate(GetParent(pNode));
                        pBrotherNode = GetParent(pNode)->pLeft;
                    }
                    if (BLACK == GetColor(pBrotherNode->pRight) && BLACK == GetColor(pBrotherNode->pLeft)){
                        SetColor(pBrotherNode, RED);
                        pNode = GetParent(pNode);
                    }
                    else{
                        if (BLACK == GetColor(pBrotherNode->pLeft)){
                            SetColor(pBrotherNode->pRight, BLACK);
                            SetColor(pBrotherNode, RED);
                            LeftRotate(pBrotherNode);
                            pBrotherNode = GetParent(pNode)->pLeft;
                        }

                        SetColor(pBrotherNode, GetColor(GetParent(pNode)));
                        SetColor(GetParent(pNode), BLACK);
                        SetColor(GetParent(pBrotherNode)->pLeft, BLACK);
                        RightRotate(GetParent(pNode));
                        pNode = m_pRoot;
                    }
                }
            }

            SetColor(pNode, BLACK);
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetMaxmum(RBTreeNode<T> *pNode) const{
            RBTreeNode<T>* pMaxNode = pNode;
            while(nullptr != pMaxNode->pRight){
                pMaxNode = pMaxNode->pRight;
            }

            return pMaxNode;
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetMinmum(RBTreeNode<T> *pNode) const{
            RBTreeNode<T>* pMinNode = pNode;
            while(nullptr != pMinNode->pLeft){
                pMinNode = pMinNode->pLeft;
            }

            return pMinNode;
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetSuccessor(RBTreeNode<T> *pNode) const{
            if (nullptr != pNode->pRight){
                return GetMinmum(pNode->pRight);
            }

            RBTreeNode<T>* pParent = GetParent(pNode);
            while (nullptr != pParent  && pParent->pRight == pNode ){
                pNode = pParent;
                pParent = GetParent(pNode);
            }

            return pParent;
        }

        template <typename T>
        RBTreeNode<T>* RBTree<T>::GetPredecessor(RBTreeNode<T> *pNode) const{
            if (nullptr != pNode->pLeft){
                return GetMaxmum(pNode->pLeft);
            }

            RBTreeNode<T>* pParent = GetParent(pNode);
            while (nullptr != pParent  && pParent->pLeft == pNode ){
                pNode = pParent;
                pParent = GetParent(pNode);
            }

            return pParent;
        }
        
        template <typename T>
        RBTreeNode<T>* RBTree<T>::SearchNode(const T& k) const{
            RBTreeNode<T>* pSearchNode = m_pRoot;
            while (nullptr != pSearchNode){
                if (pSearchNode->data == k){
                    break;
                }
                else if (pSearchNode->data > k){
                    pSearchNode = pSearchNode->pLeft;
                }
                else{
                    pSearchNode = pSearchNode->pRight;
                }
            }

            return pSearchNode;
        }

        template <typename T>
        void RBTree<T>::Clearn(RBTreeNode<T>* pNode){
            if (nullptr == pNode){
                return;
            }

            RBTreeNode<T>* pLeftNode = pNode->pLeft;
            RBTreeNode<T>* pRightNode = pNode->pRight;
            delete pNode;
            pNode = nullptr;

            if (nullptr != pLeftNode){
                Clearn(pLeftNode);
            }
            if (nullptr != pRightNode){
                Clearn(pRightNode);
            }
        }

    }
}